package leetcode.每日一题;

import leetcode.util.CommonUtils;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author ：zsy
 * @date ：Created 2022/12/15 8:00 PM
 * @description：
 */
public class 合并区间 {
    @Test
    public void test() {
        System.out.println(Arrays.deepToString(new Solution().merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}})));
    }

    class Solution {
        public int[][] merge(int[][] intervals) {
            int n = intervals.length;
            if (n == 0) return null;
            Arrays.sort(intervals, (o1, o2) -> {
                if (o1[1] != o2[1]) {
                    return o1[1] - o2[1];
                } else {
                    return o1[0] - o1[1];
                }
            });
            int right = intervals[0][1];
            int prevLeft = intervals[0][0];
            int prevRight = right;
            List<int[]> list = new ArrayList<>();
            for (int i = 1; i < n; i++) {
                if (intervals[i][0] <= right) {
                    prevRight = intervals[i][1];
                } else {
                    list.add(new int[]{prevLeft, prevRight});
                    right = intervals[i][1];
                    prevLeft = intervals[i][0];
                    prevRight = right;
                }
            }
            list.add(new int[]{prevLeft, prevRight});
            int[][] ans = new int[list.size()][2];
            for (int i = 0; i < list.size(); i++) {
                ans[i] = list.get(i);
            }
            return ans;
        }
    }
}
